package solutions.leetcode.normal

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/contest/weekly-contest-330/problems/count-collisions-of-monkeys-on-a-polygon/">2550. 猴子碰撞的方法数</a>
 */
private class Solution2550 {
    /*
    3   4   5   6   7
    8   16  32  64  128
    6   14  30  62  126
     */
    private val mod = 1000000007

    fun monkeyMove(n: Int): Int {
        return ((getRst(n) + mod - 2) % mod).toInt()
    }

    private fun getRst(n: Int): Long = if (n == 1) {
        2
    } else if (n % 2 == 1) {
        val t = getRst(n / 2)
        (2 * (t * t % mod)) % mod
    } else {
        val t = getRst(n / 2)
        ((t * t % mod)) % mod
    }
}

fun main() {
    println(Solution2550().monkeyMove(500000003))
}